iT邦幫忙

2023 iThome 鐵人賽

DAY 20
0
自我挑戰組

leetcode題目分享系列 第 20

[Day 20] 1658. Minimum Operations to Reduce X to Zero

  • 分享至 

  • xImage
  •  

slinding window 可以逐漸取得正確的涵蓋範圍,先用right開始從頭加,加到超過target就開始用left從頭減。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int target = 0;
        for(int num : nums){
            target += num;
        }
        target -= x;
        if(target == 0){
            return nums.size();
        }

        int cur = 0;
        int l = 0;
        int max_len = 0;
        for(int r = 0; r < nums.size(); r++){
            cur += nums[r];
            while(cur > target && l <= r){
                cur -= nums[l];
                l++;
            }
            if(cur == target){
                max_len = max(max_len, r - l + 1);
            }
        }
        return max_len ? nums.size() - max_len : -1;
    }
};

上一篇
[Day 19] 287. Find the Duplicate Number
下一篇
[Day 21] 4. Median of Two Sorted Arrays
系列文
leetcode題目分享30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言